import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-02-15
 * Time: 14:02
 */
public class Solution {

    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];

        if(arr == null || k == 0) {
            return ret;
        }

        //O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);

        //O(k*logN) 次数*树的高度
        for(int x : arr) {
            minHeap.offer(x);
        }

        for(int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    public static int[] maxK(int[] arr, int k) { //N*logK
        int[] ret = new int[k];

        if(arr == null || k == 0) {
            return ret;
        }

        Queue<Integer> minHeap = new PriorityQueue<>(k);

        //1.遍历数组的前K个 放到堆中  k*logK
        for(int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //2.遍历剩下的K-1个 每次和堆顶元素比较 (N-k)*logK
        // 堆顶元素 小的时候出堆
        for(int i = k; i < arr.length; i++) {
            int val = minHeap.peek();
            if(val < arr[i]) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }

        for(int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] array = {1,5,43,3,2,98,42,546,77};
        int[] ret = maxK(array,3);
        System.out.println(Arrays.toString(ret));
    }

}
